The present invention relates generally to the field of error correcting codes for data transmission and more particularly to a packet loss recovery technique for use in data packet-based networks providing real-time multimedia communications.
One of the most significant issues that must be dealt with in data packet-based communications networks such as, for example, the Internet, is the problem of error correction due to packet loss. Since each data packet is transmitted through the network independently (and potentially via entirely different network routes), it is common for a destination location to fail to receive an occasional sequence of one or more data packets, and to receive some such packets after an atypically substantial delay. And when such a network is employed to provide real-time multimedia communications such as, for example, voice communications, receiving some data packets after a substantial delay may be tantamount to not receiving them at all, since the receiver cannot typically wait to proceed with the processing of subsequent data packets.
A number of techniques, invariably involving some sort of redundancy coding, have been employed to address the general problem of error correction including the packet loss problem. Typically, the packet loss channel is recognized as an erasure channel using a channel coding language. Classical error correcting codes such as binary block codes and Reed Solomon codes, each familiar to those of ordinary skill in the art, can then be employed in an erasure correcting mode. (See, e.g., E. Ayanoglu et al., xe2x80x9cDiversity Coding for Transparent Self-Healing and Fault-Tolerant Communication Networks,xe2x80x9d IEEE Transactions on Communications, vol. 41, no. 11, pp. 1677-1685, November, 1993; and R. Urbanke el al., xe2x80x9cMethods and Apparatus for Packetizing Data for Transmission Through an Erasure Broadcast Channel,xe2x80x9d copending U.S. patent application, Ser. No. 08/892855, filed Jul. 15, 1997 and assigned to the assignee of the present invention. U.S. patent application, Ser. No. 08/892855 is hereby incorporated by reference as is fully set forth herein.) However, it is in fact considerably simpler to correct an erasure than to correct other types of errors (such as, for example, xe2x80x9crandomxe2x80x9d modifications of one or more symbols). In the case of an error, the location of the error must first be determined, while in the case of an erasure (e.g., an unreceived data packet), the location is known.
Typically, a random error correcting code can correct about twice as many erasures as errors in a given block. However, in the context of a transmission of a sequence of data packets across a network, a packet loss effectively causes a continuous string (a xe2x80x9cburstxe2x80x9d) of erased symbols. Since most classical channel codes are designed for the correction of random errors (or random erasures), prior art approaches to dealing with the packet loss problem typically perform some form of interleaving (permuting) on a relatively long sequence of packets. In this manner, a packet loss channel with correlated erasures (i.e., a continuous string of erased symbols) is transformed into an apparently random erasure channel. Unfortunately, performing such an interleaving process necessarily results in a significant delay at the destination, since the decoder must de-interleave the received data in order to recreate the original sequence of data packets.
Therefore, the use of channel codes such as, for example, Reed Solomon codes, when effectively applied across many packets in sequence, will necessarily require that relatively long delays be incurred at the receiver. As pointed out above, however, such delays may be prohibitive for real-time applications such as, for example, voice communication over networks based on the Internet protocol (IP). Recently, however, in U.S. Pat. No. 5.870,412 (xe2x80x9cForward Error Correction System for Packet Based Real Time Mediaxe2x80x9d) issued to G. M. Schuster et al. on Feb. 9, 1999 (hereinafter, xe2x80x9cSchuster et al.xe2x80x9d), a method for data recovery in a bursty packet network which incurs a relatively short delay (as compared to other prior art techniques) has been presented.
Specifically, Shuster et al. performs forward error correction by appending checksum information to each data packet, wherein the checksum information is defined by taking a bit-by-bit exclusive-or sum of the information portion (the xe2x80x9cpayloadxe2x80x9d) from a preceding specified number of data packets. (Bit padding on the shorter payloads is used if the information payloads from the preceding packets are of unequal length.) By way of illustration, FIG. 1 shows a conceptual organization of a transmitted data packet in accordance with certain prior art packet loss recovery techniques, such as that employed in Shuster et al. The illustrated data packet comprises control information 11 followed by associated payload information 12. The payload information comprises the actual data which is to be communicated across the network with use of the particular packet. In addition, and in accordance with the illustrative prior art techniques such as Shuster et al., checksum information 13 is appended to the data packet for purposes of error correction. As described above, in the case of the Shuster et al. technique, the checksum information specifically comprises an exclusive-or sum of the information payload from a preceding specified plural number of data packets.
Thus, using the Shuster et al. technique, a single bit erasure correction code of length w+l packet instances is formed, enabling for the correction of a burst of up to w lost data packets (provided such a burst is followed by a string of w correctly received data packets), with a maximum decoding delay of 2w packets. Clearly, the Shuster et al. method incurs an overhead in bit volume of at least 100% (more if bit padding is required), as compared to the bits of the information payloads alone. In addition, it can be seen that the method of Shuster et al. requires the solution of w exclusive-or equations.
We have recognized that a significant improvement over the scheme of Shuster et al. may be realized by foregoing the prior art""s approach of generating checksum information by xe2x80x9ccombiningxe2x80x9d (e.g., by performing exclusive-or operations) the payload information from a plurality of preceding data packets, and rather, simply xe2x80x9crepeatingxe2x80x9d information content from a particular one of the previous data packets. For example, and in accordance with a first illustrative embodiment of the present invention, the information payload associated with a given data packet k is identically copied and appended to data packet k+w. That is, the information payload is repeated with a delay of w transmitted packets. Such an approach can advantageously correct for a burst of up to w lost data packets (as does the prior art method of Shuster el al.), but no complex mathematical operations (such as the exclusive-or operations required by Shuster el al.) need to be performed. Moreover, and most importantly, the illustrative method of the present invention improves the decoding window (i.e., the maximum decoding delay) to w+l packets (as compared to the 2w packet decoding window required by the method of Shuster et al.
In accordance with one illustrative embodiment of the present invention, the value of the parameter w may be advantageously selected based on any desired xe2x80x9cburstxe2x80x9d error (i.e. the number of consecutive lost packets) correction capability, in combination with a corresponding desired xe2x80x9cdecoding windowxe2x80x9d (i.e., the maximum decoding delay), since the setting of parameter w clearly results in a direct tradeoff between these two factors. In accordance with another illustrative embodiment of the present invention, the value of the parameter w may be set or adjusted dynamically based on network feedback information.
Specifically, the present invention provides a method of coding a sequence of data packets representing a continuous stream of information, with each data packet comprising a set of payload information representative of a segment of the stream of information corresponding thereto. The method comprises the steps of coding a first data packet for transmission (wherein the encoded first data packet comprises a first set of payload information representative of a first segment of the stream of information), and coding a second data packet subsequent to the first data packet in the sequence for transmission (wherein the encoded second data packet comprises a second set of payload information representative of a second segment of the stream of information subsequent to the first segment of the stream of information). The encoded second data packet further comprises an additional set of payload information, the additional set of payload information also representative of the first segment of the stream of information, but not representative of other segments of the stream of information.